package com.learn.algorithm_88;

import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * 合并两个有序数组，合并后依然有序
 * https://leetcode-cn.com/problems/merge-sorted-array/
 */
public class MergeArrays {

    public static void main(String[] args) {
        // test1
        int[] nums1 = {1,2,3,0,0,0};
        int[] nums2 = {2,5,6};
        new MergeArrays().merge(nums1, 3, nums2, 3);

        // test2
        int[] nums3 = {0};
        int[] nums4 = {1};
        new MergeArrays().merge(nums3, 0, nums4, 1);

        System.out.println("合并后num1: "+ Arrays.stream(nums1).boxed().collect(Collectors.toList()));
    }

    /**
     * @param nums1 按 非递减顺序 排列的整数数组
     * @param m nums1元素数目
     * @param nums2 按 非递减顺序 排列的整数数组
     * @param n nums2元素数目
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 取合并后最后一位下标
        int p = m-- + n-- - 1;
        // 目的是把n个元素合并到nums1，所以以n为截止数
        while (n >= 0) {
            // 存在n>=0，但m<0，此时赋值处理nums2即可
            // 比较nums1和nums2的最后一位，取较大的放入尾部，取数的数组下标前移，再进行下一轮末尾比较
            nums1[p--] = m >=0 && nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
    }

}
